Communication in a computer network involves the exchange of data between two or more entities interconnected by communication links and subnetworks. These entities are typically software programs executing on hardware computer platforms, such as end nodes and intermediate nodes. An example of an intermediate node is a switch or router which interconnects the links and subnetworks to enable transmission of data between the end nodes. The nodes typically communicate by exchanging discrete packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Most networks are typically organized as a protocol stack of hardware and software "layers" within each node of the network. The protocol stack layers interact to format data for transfer between, e.g., a source node and a destination node communicating over the network. Specifically, predetermined services are performed on the data as it passes through each layer and the layers communicate with each other by means of the predefined protocols. This layered design permits each layer to offer selected services to other layers using a standardized interface that shields those layers from the details of actual implementation of the services.
One such selected service is a connectionless network service that is generally implemented by a network layer protocol. Network layer protocols are concerned with the routing of packets from the source node to the destination node and, in particular, comprise those algorithms and protocols used by routers when cooperating to calculate paths through a network topology. A routing algorithm is that portion of the network layer software responsible for determining an output communication link over which an incoming packet should be transmitted. To that end, each router maintains a forwarding database table with entries indicating where to forward the packets in accordance with routing algorithm results. The forwarding database entries are typically accessed by referencing addresses of the destination nodes.
Examples of conventional network layer protocols are the ISO Connectionless Network Layer Protocol (CLNP), the Internet (IP) network layer protocol and the Internetwork Packet Exchange (IPX), whereas an example of a conventional routing algorithm is the Dijkstra algorithm. A by-product of execution of the Dijkstra algorithm is a determination of the next hop, e.g., intermediate router, associated with a particular calculated path.
Each protocol stack layer of a transmitting node adds information in the form of a header field to the data packet generated by a sending process of the node as the packet descends the protocol stack. The header fields defined by the network layer services are generally the same primarily because the same information are typically contained in each packet. For example, these headers typically contain fixed-length, hierarchical network layer addresses configured to accommodate relatively large numbers of nodes and subnetworks.
A destination address is used by the routers to determine the route of the packet. When a packet is received at the router, the network layer extracts the destination address from the packet, finds a forwarding database table entry that matches the destination address, determines the next hop that the packet should take based upon the destination address, appends a new network layer header onto the packet (as necessary) and passes the modified packet to a lower protocol stack layer that is responsible for the output communication link associated with the next hop.
Since network layer addresses are hierarchical in nature, network layer protocols that perform routing functions at the same routing level of a network make next hop determinations based upon a similar portion of the destination address referred to as the destination address prefix. Routers store the destination address prefixes in dictionaries of their forwarding databases as tree data structures that are manipulated by a conventional Trie algorithm. To determine the next hop, network layer protocols implement a longest-matching-address-prefix ("longest match") algorithm that searches the dictionary for an entry corresponding to the destination address located in the network layer header.
The tree structure typically comprises a large number of branches each representing a string of the hierarchical destination address fields. The branches of the database have different address field values and/or terminate with a different number of address fields. The longest match algorithm must traverse numerous branches during this address matching process to determine the next hop. Because of the hierarchical characteristics of destination addresses, there may be several destination address prefixes in the dictionary that match at least a portion of a particular destination address. Accordingly, the longest address in the forwarding database dictionary must be found.
The time required to search the dictionary is proportional to the average length of the destination address in the database. In a typical implementation of the Trie algorithm, a fixed portion of the destination address is parsed at discrete steps, e.g., one bit or 4 bits at a time. A problem is that addresses often have a substantial number of bits, particularly in large, hierarchically-arranged networks. Parsing such a long address in small increments results in too many "lookups" into the database table, a process that is often too slow to keep up with table access bandwidth. On the other hand, parsing the address in longer increments, e.g., 16 bits, can result in a substantial number of choices that consume a substantial amount of table space.
It is thus apparent that, due to the lengths of the destination addresses and the manner in which the longest match algorithm navigates the forwarding database dictionary, address matching functions contribute significantly to the overhead associated with the packet forwarding process performed by network layer protocols; this, in turn, adversely affects the router's efficiency. The present invention is directed towards an efficient and accurate means for finding the longest match in a forwarding database dictionary that matches an address in a packet to be forwarded by an intermediate node.